/**
 *  @file Locate.c
 *  @desc 基于访问频率对双向链表进行动态调整
 *        每次访问某个元素时，其频率加一，并将该节点按 freq 降序重新插入链表
 *  @author WangBlue(wangjiping596@gmail.com)
 *  @date 2025-07-25
 *  @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>

// 链表节点结构体，包含数据、访问频率、前驱、后继指针
typedef struct node {
    int data;
    int freq;
    struct node *next;
    struct node *pre;
} node, *link;

// 创建一个新节点，初始化 data 和 freq
link createNode(int value) {
    link newNode = (link) malloc(sizeof(node));
    if (newNode == NULL) return NULL;
    newNode->data = value;
    newNode->freq = 0;
    newNode->next = NULL;
    newNode->pre = NULL;
    return newNode;
}

// 初始化头节点（头节点本身不存储数据）
void initNode(link *head) {
    link newNode = createNode(0);
    if (newNode == NULL) return;
    *head = newNode;
}

// 尾插：将新节点插入链表末尾（默认 freq 为 1）
void istTail(link head, int value) {
    link cur = head;
    // 找到尾节点
    while (cur->next != NULL) {
        cur = cur->next;
    }

    link newNode = createNode(value);
    if (newNode == NULL) return;

    newNode->freq++;  // 初始插入时访问频率设为 1
    cur->next = newNode;
    newNode->pre = cur;
}

// 打印链表中每个节点的值和访问频率
void printList(link head) {
    if (head == NULL || head->next == NULL) return;
    link cur = head->next;
    while (cur != NULL) {
        printf("value is %d  freq is %d\n", cur->data, cur->freq);
        cur = cur->next;
    }
}

// locate 函数：查找值为 x 的节点，访问频率 +1，然后按频率重新排序
void locate(link head, int x) {
    if (head == NULL || head->next == NULL) return;

    // 1. 查找目标节点
    link cur = head->next;
    while (cur != NULL && cur->data != x) {
        cur = cur->next;
    }

    if (cur == NULL) return; // 没找到目标值

    // 2. 访问频率 +1
    cur->freq++;

    // 3. 将该节点从原位置“摘除”
    cur->pre->next = cur->next;
    if (cur->next != NULL) {
        cur->next->pre = cur->pre;
    }

    // 4. 从头开始寻找插入位置：找到第一个 freq <= cur->freq 的节点
    link istTemp = head->next;
    while (istTemp != NULL && istTemp->freq > cur->freq) {
        istTemp = istTemp->next;
    }

    // 5. 重新插入 cur 节点到合适位置之前
    link pre;
    if (istTemp == NULL) {
        // 插到链表尾部
        pre = head;
        while (pre->next != NULL) pre = pre->next;
    } else {
        // 插入到 istTemp 前面
        pre = istTemp->pre;
    }

    // 执行插入操作
    cur->next = pre->next;
    cur->pre = pre;

    if (pre->next != NULL) {
        pre->next->pre = cur;
    }
    pre->next = cur;
}

// 主函数测试
int main() {
    link head = NULL;
    initNode(&head);

    // 初始化链表：1 -> 2 -> 3（初始频率为 1）
    istTail(head, 1);
    istTail(head, 2);
    istTail(head, 3);

    // 模拟访问顺序，影响频率和最终位置
    locate(head, 1);   // freq: 2
    locate(head, 3);   // freq: 2
    locate(head, 3);   // freq: 3
    locate(head, 3);   // freq: 4
    locate(head, 2);   // freq: 2
    locate(head, 2);   // freq: 3
    locate(head, 2);   // freq: 4
    locate(head, 2);   // freq: 5
    locate(head, 1);   // freq: 3
    locate(head, 1);   // freq: 4

    // 打印最终链表（按 freq 降序）
    printList(head);

    return 0;
}
